package com.hy.study.practice.recursion;

import java.util.Scanner;

public class Queue8ByDoubleArray2 {
    static int nnn = 8;
    static int sum = 0;
    static int x[][] = new int[nnn][nnn];

    public static void main(String args[]) {
        backtrace(0);
        System.out.println(sum);
    }

    static void backtrace(int t) {
        if (t >= nnn) {
            sum++;
            for (int i = 0; i < nnn; i++) {
                for (int j = 0; j < nnn; j++)
                    System.out.print(x[i][j] + " ");
                System.out.println();
            }
            System.out.println("-----------------");
        }
        for (int j = 0; j < nnn; j++)
            if (check(t, j)) {
                x[t][j] = 1;
                backtrace(t + 1);
                x[t][j] = 0;
            }

    }

    static boolean check(int m, int n) {
        for (int i = 0; i < m; i++) {
            if (x[i][n] == 1)
                return false;
        }
        for (int i = 0; i < n; i++) {
            if (x[m][i] == 1)
                return false;
        }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (x[i][j] == 1 && Math.abs(m - i) == Math.abs(n - j))
                    return false;
            }
        for (int i = 0; i < m; i++)
            for (int j = nnn - 1; j > n; j--) {
                if (x[i][j] == 1 && Math.abs(m - i) == Math.abs(n - j))
                    return false;
            }

        return true;
    }

}
